package week1;

/**
 * Created by YanChenDeng on 2016/10/13.
 * Abstract class for Union-Find algorithms
 */
public abstract class UF {
    protected int[] id;
    private int connectedComponentCount;
    /**
     * Constructor
     * @param n number of sites
     * */
    public UF(int n){
        id = new int[n];
        connectedComponentCount = n;
        for (int i = 0; i < n; i++)
            id[i] = i;
    }
    /**
     * Add a connection between p and q
     * */
    public void union(int p,int q){
        if (!connected(p,q))
            connectedComponentCount--;
    }
    /**
     * Test the connectedness between p and q
     * @return true if p and q are connected
     * */
    public abstract boolean connected(int p,int q);
    /**
     * Calculate the connected component of p
     * @return id of connected component of p
     * */
    public abstract int find(int p);
    /**
     * Calculate the number of connected component
     * @return number of connected components
     * */
    public int count(){
        return connectedComponentCount;
    }
}
